package com.gofaraway.service.左神算法课.heap;


import static com.gofaraway.service.utils.AlgorithmUtils.swap;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author ChenPeng
 * @since 2025/2/16 15:56
 */
public class Code02_Heap {


    /**
     * 往堆里面添加元素 大根堆
     * 1.新加进来的元素 现在停在了index位置 需要依次往上移动
     * 2.移动到 0 位置 或者干不掉自己的父亲 停
     *
     * @param arr 数组
     * @param index 需要入堆的元素下标
     */
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }


    /**
     * 指定元素下标 将该数在堆中下沉 维持堆结构
     * 1.从index位置 往下看 不断的下沉 维持（大根堆）堆结构
     * 2.终止条件：较大的孩子都不比 index位置的数大 或 已经没有孩子了
     *
     * @param arr
     * @param index
     * @param heapSize
     */
    public static void heapify(int[] arr, int index, int heapSize) {

        int left = index * 2 + 1;
        while (left < heapSize) {
            //把较大孩子的下标 给largest
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;

            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void main(String[] args) {
        //默认小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.add(5);
        heap.add(3);
        System.out.println(heap.peek());

        System.out.println("大根堆");
        PriorityQueue<Integer> heap1 = new PriorityQueue<>((o1, o2) -> o2  -o1);
        heap1.add(5);
        heap1.add(3);
        System.out.println(heap1.peek());
    }

}
